As it is known in the art, computer processing systems include a central processing unit which operates on data stored in a memory. Increased computer processing performance is often achieved by including a smaller, faster memory, called a cache, between the central processing unit and the memory for temporary storage of the memory data. The cache reduces the delay associated with memory access by storing subsets of the memory data that can be quickly read and modified by the central processing unit.
Because computer processes commonly reference memory data in contiguous address space, data is generally obtained from memory in blocks. There are a variety of methods used to map blocks of data from memory into the cache. Two typical cache arrangements include direct mapped caches and set associative caches.
In a conventional direct mapped cache, a block of data from memory is mapped into the cache using the lower bits of the memory address. The lower bits of the memory address are generally called the cache index. The upper bits of the memory address of the data block are generally called the `tag` of the block. A tag store, which generally has a number of locations equivalent to the number of blocks in the cache, is used to store the tag of each block of data in the cache.
When a processor requires data from the cache it addresses the cache and the tag store and compares the received tag to the upper bits of the memory address of the required data. If the data is not in the cache, the tag does not match the upper address bits and there is a `miss` in the cache. When there is a `miss`, a memory read is performed to fill the cache with the required data. It is desirable to minimize the number of cache misses in order to avoid the latency incurred by the resulting memory reference.
Direct mapped caches are advantageous because they provide a cache system with minimal address complexity. Because the addressing scheme is straightforward, the cache is able to quickly return data to the central processing unit. However, one drawback of direct mapped caches is that since there is only one possible location in the cache for data having a common cache index, the miss rate is generally high. Thus, although direct mapped caches are able to quickly return data to the central processing unit, the performance is greatly reduced by the high miss rates inherent in the system.
Set associative caches serve to reduce the amount of misses by providing multiple cache locations for memory data having a common cache index. In set-associative caching, the cache is subdivided into a plurality of `sets`. Each set has an associated tag store for storing the tags of the blocks of data stored in the set. As in direct mapped caching, the location of a particular item within the cache is identified by a cache index derived from the lower bits of the memory address.
When the processor wants to fetch data from the cache, the cache index is used to address each of the sets and their associated tag stores. Each set outputs a data item located at the cache index and the data items sets are generally input to a large multiplexer. The associated tags are each compared against the upper bits of the main memory address to determine if any data item provided by the sets is the required data item. Assuming that the data item to be fetched is in one of the sets of cache, the tag output by the tag store associated with the set matches the upper bits of the memory address. Depending on which tag matched, the appropriate select is provided to the multiplexer and the required data is returned to the processor.
Set-associative cache mapping thus provides improved performance over a direct mapped cache by reducing the frequency of cache misses. However, the amount of time required to perform the set comparison makes the set-associative cache memory system a relatively slow system compared to the direct mapped cache system.
Typically in cache subsystem design a tradeoff is made between the performance advantage provided by the addressing method of direct mapped caches and the reduced miss rate inherent in set-associative caches. It would be desirable to provide a cache subsystem which would be able to utilize the advantages of both the set associative and direct mapped designs with minimal hardware complexity.